#pragma once
#include <iostream>
#include <cstdlib>
#include <ctime>
#define MAX(a,b) (a>b)?a:b
#define MAXSIZE 1024
using namespace std;
class INT
{
public:
	int len;
	unsigned char d[MAXSIZE];
	INT() { memset(d, 0, MAXSIZE); };
	~INT() {};
	void operator= (const INT&);
	void operator= (const int& a);
	void Clear() { memset(d, 0, MAXSIZE); }
	INT Random();
	void RefreshLen();
};
void INT::RefreshLen() {
	int count = 0;
	bool flag = true;
	for (int i = 0; i < MAXSIZE; i++) {
		if (d[i] == 0) { count++; }
		else { len = count; return; }
	}
	len = MAXSIZE;
}
void INT::operator= (const int& a) {
	int temp = a;
	Clear();
	for (int i = MAXSIZE - 1; i > MAXSIZE - 32; i--) {
		d[i] = temp & 1;
		temp >>= 1;
	}
}
ostream& operator<< (ostream& out, const INT& a) {
	int count = 1;
	char list[] = "0123456789ABCDEF";
	bool flag = true;//��������ǰ��0
	for (int i = 0; i < MAXSIZE; i += 4) {
		int num = (a.d[i] << 3) + ((a.d[i + 1]) << 2) + ((a.d[i + 2]) << 1) + ((a.d[i + 3]));
		if (flag && num == 0) { continue; }
		else if (flag && num) { flag = false; }
		out << list[num];
		if (count++ % 8 == 0)out << " ";
	}
	if (flag)out << 0;
	return out;
}
istream& operator>>(istream& in, INT& a) {
	string s;//输入十六进制
	in >> s;
	int idx = MAXSIZE - 1;
	for (int i = s.length() - 1; i > -1; i--) {
		switch (s[i])
		{
		case '0':
			a.d[idx - 3] = 0; a.d[idx - 2] = 0; a.d[idx - 1] = 0; a.d[idx] = 0;
			break;
		case '1':
			a.d[idx - 3] = 0; a.d[idx - 2] = 0; a.d[idx - 1] = 0; a.d[idx] = 1;
			break;
		case '2':
			a.d[idx - 3] = 0; a.d[idx - 2] = 0; a.d[idx - 1] = 1; a.d[idx] = 0;
			break;
		case '3':
			a.d[idx - 3] = 0; a.d[idx - 2] = 0; a.d[idx - 1] = 1; a.d[idx] = 1;
			break;
		case '4':
			a.d[idx - 3] = 0; a.d[idx - 2] = 1; a.d[idx - 1] = 0; a.d[idx] = 0;
			break;
		case '5':
			a.d[idx - 3] = 0; a.d[idx - 2] = 1; a.d[idx - 1] = 0; a.d[idx] = 1;
			break;
		case '6':
			a.d[idx - 3] = 0; a.d[idx - 2] = 1; a.d[idx - 1] = 1; a.d[idx] = 0;
			break;
		case '7':
			a.d[idx - 3] = 0; a.d[idx - 2] = 1; a.d[idx - 1] = 1; a.d[idx] = 1;
			break;
		case '8':
			a.d[idx - 3] = 1; a.d[idx - 2] = 0; a.d[idx - 1] = 0; a.d[idx] = 0;
			break;
		case '9':
			a.d[idx - 3] = 1; a.d[idx - 2] = 0; a.d[idx - 1] = 0; a.d[idx] = 1;
			break;
		case 'A':case 'a':
			a.d[idx - 3] = 1; a.d[idx - 2] = 0; a.d[idx - 1] = 1; a.d[idx] = 0;
			break;
		case 'B':case 'b':
			a.d[idx - 3] = 1; a.d[idx - 2] = 0; a.d[idx - 1] = 1; a.d[idx] = 1;
			break;
		case 'C':case 'c':
			a.d[idx - 3] = 1; a.d[idx - 2] = 1; a.d[idx - 1] = 0; a.d[idx] = 0;
			break;
		case 'D':case 'd':
			a.d[idx - 3] = 1; a.d[idx - 2] = 1; a.d[idx - 1] = 0; a.d[idx] = 1;
			break;
		case 'E':case 'e':
			a.d[idx - 3] = 1; a.d[idx - 2] = 1; a.d[idx - 1] = 1; a.d[idx] = 0;
			break;
		case 'F':case 'f':
			a.d[idx - 3] = 1; a.d[idx - 2] = 1; a.d[idx - 1] = 1; a.d[idx] = 1;
			break;
		default:
			break;
		}
		idx -= 4;
	}
	return in;
}
INT operator>> (const INT& a, int b) {
	INT res;
	for (int i = b; i < MAXSIZE; i++) {
		res.d[i] = a.d[i - b];
	}
	return res;
}
INT operator<< (const INT& a, int b) {
	INT res;
	for (int i = 0; i < MAXSIZE - b; i++) {
		res.d[i] = a.d[i + b];
	}
	return res;
}
void INT::operator= (const INT& input) {
	memset(d, 0, MAXSIZE);
	memcpy(this, &input, sizeof(INT));
}
INT operator+ (const INT& a, const INT& b) {
	//1023 
	INT res;
	unsigned char carry = 0;
	for (int i = MAXSIZE - 1; i > 500; i--) {
		res.d[i] = a.d[i] + b.d[i] + carry;
		if (res.d[i] > 1) {
			carry = 1;
			res.d[i] -= 2;
		}
		else carry = 0;
	}
	return res;
}
INT operator- (const INT& a, const INT& b) {
	INT res;
	unsigned char carry = 0;
	for (int i = MAXSIZE - 1; i > 500; i--) {
		if (a.d[i] < b.d[i] + carry) {
			res.d[i] = a.d[i] + 2 - b.d[i] - carry;
			carry = 1;
		}
		else {
			res.d[i] = a.d[i] - b.d[i] - carry;
			carry = 0;
		}
	}
	return res;
}
INT operator* (INT a, INT& b) {
	INT res;
	b.RefreshLen();
	for (int i = MAXSIZE - 1; i >= b.len; i--) {
		if (b.d[i]) {//1
			res = res + a;
		}
		a = (a << 1);
	}
	return res;
}
bool operator> (const INT& a, const INT& b) {
	for (int i = 0; i < MAXSIZE; i++) {
		if (a.d[i] > b.d[i])return true;
		else if (a.d[i] < b.d[i])return false;
	}
	return false;
}
bool operator== (const INT& a, const INT& b) {
	for (int i = 0; i < MAXSIZE; i++) {
		if (a.d[i] != b.d[i])return false;
	}
	return true;
}
bool operator!= (const INT& a, const INT& b) {
	for (int i = 0; i < MAXSIZE; i++) {
		if (a.d[i] != b.d[i])return true;
	}
	return false;
}
bool operator< (const INT& a, const INT& b) {
	for (int i = 0; i < MAXSIZE; i++) {
		if (a.d[i] < b.d[i])return true;
		else if (a.d[i] > b.d[i])return false;
	}
	return false;
}
bool operator<= (const INT& a, const INT& b) {
	for (int i = 0; i < MAXSIZE; i++) {
		if (a.d[i] < b.d[i])return true;
		else if (a.d[i] > b.d[i])return false;
	}
	return true;
}
bool operator>= (const INT& a, const INT& b) {
	for (int i = 0; i < MAXSIZE; i++) {
		if (a.d[i] > b.d[i])return true;
		else if (a.d[i] < b.d[i])return false;
	}
	return true;
}
INT operator%(INT a, INT& b) {//a%b
//100000	MAXSIZE-6
//   110	MAXSIZE-3
	if (a < b)return a;
	while(a>=b){
		a.RefreshLen();
		b.RefreshLen();
		int diff = b.len-a.len;
		INT t = b<<diff;
		if(a>=t)a=a-t;
		else a=a-(t>>1);
	}
	return a;
}
INT operator/ (INT a, INT& b) {
	INT res;
	INT ONE; ONE = 1;
	//1100100 MAXSIZE-7
	//     10 MAXSIZE-2
	//res:100000 dif=5
	

	//100100  MAXSIZE-6
	//	  10  MAXSIZE-2
	//res<<1->10
	//res:110000 dif=4

	//100	  MAXSIZE-3
	// 10	  MAXSIZE-2
	//res<<3->11000
	//res:110010 dif=1
	int last_dif=0;
	while(a>=b){
		a.RefreshLen();
		b.RefreshLen();
		int diff = b.len-a.len;
		if(last_dif){res = res<<(last_dif-diff);}
		last_dif=diff;
		INT t = b<<diff;
		if(a>=t){a=a-t;res = res+ONE;}
		else {a=a-(t>>1);}
		//res = res<<diff;
	}
	if(last_dif){res = res<<(last_dif);}
	return res;
}
INT INT::Random() {
	d[MAXSIZE - 1] = 1;
	for (int i = MAXSIZE - 2; i > 512; i--)
	{
		d[i] = rand() % 2;
	}
	d[MAXSIZE - 512] = 1;
	return *this;
}
INT mod_mul(INT& a, INT& b, INT& n) {
	INT res;
	res = a * b;
	if (res < n)return res;
	res = res%n;
	// while (res > n) {
	// 	res = res - n;
	// }
	// if (res == n)res.Clear();
	//cout<<"a*b mod n="<<res<<endl;
	return res;
}
INT mod_exp(INT a, INT b, INT n)
{
	INT res; res = 1;
	INT ONE; ONE = 1;
	b.RefreshLen();
	int len = b.len;
	while (len < MAXSIZE) {
		if (b.d[MAXSIZE - 1])res = mod_mul(res, a, n);
		b = b >> 1;
		a = mod_mul(a, a, n);
		len++;
	}
	return res;
}
bool isPrime(INT n) {
	INT THREE; THREE = 3;
	INT ONE; ONE = 1;
	if (n < THREE) // 特判1，2
		return n.d[MAXSIZE - 2];
	if (n.d[MAXSIZE - 1] == 0) // 特判偶数
		return false;
	//static const unsigned int A[] = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };

	INT m = n - ONE;
	INT mm; mm = m;
	int k = 0;
	for (int i = MAXSIZE - 1;; i--) {
		if (m.d[i])break;
		k++;
	}
	m = m >> k;

	INT a;
	for (int p = 0; p < 4; p++) {

		//a = a - ONE;
		a.Random();
		cout << "Random Num a:" << a << endl;

		a =a% mm;
		// while (a > mm) {
		// 	a = a - mm;
		// }
		// if (a == mm)a.Clear();


		INT v; v = mod_exp(a, m, n); // a^m % n
		cout << "v:" << a << endl;
		// 检验成功 v = -1, 1
		if (v == ONE)continue;
		for (int i = 1; i <= k; i++) {//循环k次
			if (i == k)return false;
			else if (v == n - ONE) {//本轮通过
				//v = 1;
				break;
			}
			v = mod_mul(v, v, n);
		}
	}
	return true;
}
INT str2INT(string s) {
	INT a;
	int idx = MAXSIZE - 1;
	for (int i = s.length() - 1; i > -1; i--) {
		int diff = 0;
		while (s[i]) {
			a.d[idx - diff++] = s[i] & 1;
			s[i] = s[i] >> 1;
		}
		idx -= 8;
	}
	return a;
}
INT exgcd(INT a, INT b, INT& x, INT& y) {
	//cout << "a:" << a << endl << "b:" << b << endl << endl;
	b.RefreshLen();
	if (b.len == MAXSIZE) {
		x = 1;
		y = 0;
		return a;
	}
	INT d = exgcd(b, a % b, y, x);
	y = y - (a / b) * x;
	return d;
}
INT niyuan(INT a, INT b)//求a对b取模的逆元
{
	INT x, y;
	INT aa = exgcd(a, b, x, y);
	//x,y值已经出来了,aa可以扔掉了
	return (x + b) % b;
}
INT GCD(INT a, INT b)
{
	//cout << "a:" << a << endl << "b:" << b << endl << endl;
	b.RefreshLen();
	if (b.len == MAXSIZE)
		return a;
	return GCD(b, a % b);
}
INT all(INT&a){
	for(int i=0;i<MAXSIZE;i++){
		a.d[i]=1;
	}
}
INT encode(string s) {
	INT ZERO; ZERO = 0;//常数0
	INT ONE; ONE = 1;//常数1
	INT TWO; TWO = 2;//常数2
	INT m = str2INT(s);//明文
	cout<<"m:"<<m<<endl;
	//产生两个大素数
	INT p;//p.Random();
	cout << "p:" ; cin>>p; //cout<<"p:"<< p << endl;
	INT q; //q.Random();
	cout << "q:";cin>>q;//cout << q << endl;
	INT n; n = p * q;
	cout << "n:" << n << endl;
	INT phi; phi = n - p - q + ONE;
	cout << "phi:" << phi << endl;
	INT e; e = 65537;
	while (GCD(phi, e) != ONE) { e = e + TWO; cout << e << endl; }
	cout << "e:" << e << endl;
	INT d; d = niyuan(e, phi);
	cout << "d:" << d << endl;
	INT c; c = mod_exp(m,e,n);
	cout<<"c:"<<c<<endl;

	m = mod_exp(c,d,n);
	cout<<"m:"<<m<<endl;
	cout<<"c:"<<mod_exp(m,e,n)<<endl;

	cout << "finish!" << endl;
	return str2INT(s);
}